public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        // System.out.println(test.mySqrt(2147483647));

        // int[] nums = new int[]{1,3,5,6};
        // System.out.println(test.searchInsert(nums, 0));

        int[] arr = new int[]{1,2,3,4,1};
        System.out.println(test.peakIndexInMountainArray(arr));
    }

    public int mySqrt(int x) {
        /**
         * x的平方根
         * 本题为查找左端点，唯一需要注意的是：本题x的取值为int最大值，存在溢出的风险，因此建议使用long进行接收
         * */
        // 1 双指针
        long left = 0;
        long right = x;
        while(left < right) {
            long mid = left + (right - left + 1) / 2;
            // -此处溢出了
            if(mid * mid <= x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return (int)left;
    }

    public int searchInsert(int[] nums, int target) {
        /**
         * 搜索插入位置
         * 使用二分查找左边界算法进行实现*/
        // 1 预处理
        int n = nums.length;

        // 2 双指针
        int left = 0;
        int right = n - 1;
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        // 3 返回值
        if(nums[left] == target) {
            // -相等就直接返回
            return left;
        } else if(nums[left] < target) {
            // -当前分界值小于目标值，那么插入该元素后
            return left + 1;
        } else {
            // -当前分界值大于目标值，那么插入该元素前，但是需要注意下标问题，不得小于0
            return left == 0 ? 0 : left -1;
        }
    }

    public int peakIndexInMountainArray1(int[] arr) {
        /**
         * 山脉数组的峰顶
         * 解法：暴力解法（太简单），使用双指针解法
         * 双指针即是根据元素的大小关系确定二段性*/
        // 1 预处理
        int n = arr.length;

        // 2 双指针
        int left = 0;
        int right = n-1;
        while(left <= right) {
            int mid = left + (right - left + 1) / 2;
            if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
                return mid;
            } else if(arr[mid-1] < arr[mid] && arr[mid] < arr[mid + 1]) {
                // -注意：因为选择的是右中心点，因此当left步进时不可以+1，否则会越界访问
                left = mid;
            } else if(arr[mid-1] > arr[mid] && arr[mid] > arr[mid + 1]) {
                right = mid - 1;
            }
        }
        return -1;
    }

    public int peakIndexInMountainArray(int[] arr) {
        /**
         * 山脉数组的峰顶
         * 解法：二分查找左区间优化*/
        // 1 预处理
        int n = arr.length;

        // 2 双指针
        int left = 0;
        int right = n-1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(arr[mid] >= arr[mid+1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
